package cn.walls1717.leetcode.array;

/**
 * 27. 移除元素
 * 力扣地址：https://leetcode-cn.com/problems/remove-element/
 *
 * @author walls1717
 * @since 2022-04-30
 **/
public class T27 {

    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 2, 3, 0, 4, 2};
        int val = 2;
        int index = removeElement(nums, val);
        for (int i = 0; i < index; i++) {
            System.out.print(nums[i]);
        }
    }

    /**
     * 暴力破解
     *
     * @param nums 数组
     * @param val 要删除的值
     * @return 删除后数组的大小
     */
    public static int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; ++i) {
            // 发现需要移除的元素，就将数组集体向前移动一位
            if (nums[i] == val) {
                for (int j = i + 1; j < size; ++j) {
                    // 用这样的方式可以防止数组越界
                    nums[j - 1] = nums[j];
                }
                // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                // 保证了要删除的数在数组中连续存在也可以删除成功
                --i;
                // 此时数组的大小-1
                // 保证输出正确的数组大小，保证循环正常结束
                --size;
            }
        }
        return size;
    }

    /**
     * 双指针法
     *
     * @param nums 数组
     * @param val 要删除的值
     * @return 删除后数组的大小
     */
    public static int removeElement2(int[] nums, int val) {
        // 快慢指针
        int fastIndex = 0;
        int slowIndex;

        for (slowIndex = 0; fastIndex < nums.length; ++fastIndex) {
            // 如果不是要删除的数，快慢指针同时移动，否则只有快指针移动
            // 当快指针移动到不是要删除的数时，将此数据覆盖慢指针对应的数据
            // 慢指针移动，快指针移动，确保了要删除的数连续存储也能正常删除
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                ++slowIndex;
            }
        }
        // 此时满指针的大小就是删除后数组的大小
        return slowIndex;
    }
}
